/*
 * @lc app=leetcode id=42 lang=cpp
 *
 * [42] Trapping Rain Water
 */
class Solution {
public:
    int trap(vector<int>& height) {
        int len = height.size();
        if (len < 3) {
            return 0;
        }

        vector<int> leftHeight(len, 0);
        vector<int> rightHeight(len, 0);

        leftHeight[0] = height[0];
        rightHeight[len-1] = height[len-1];
        for (int i=1; i<len; i++) {
            leftHeight[i] = std::max(leftHeight[i-1], height[i]);
        }

        for (int i=len-2; i>0; i--) {
            rightHeight[i] = std::max(rightHeight[i+1], height[i]);
        }

        int i, j, sum = 0;
        int leftMost, rightMost, minHeight;
        for (int idx=1; idx<len-1; idx++) {
            leftMost = leftHeight[i-1];
            rightMost =  rightHeight[i+1];
            minHeight = std::min(leftMost, rightMost);
            if (minHeight > height[idx]) {
                sum += minHeight - height[idx];
            }
        }
        return sum;
    }
};

